package bfsalgorithm;

import java.util.*;

/**
 * LCR 114.火星词典
 */
public class Exercise14 {
    Map<Character,Set<Character>> edges = new HashMap<>(); // 用于建图
    Map<Character,Integer> in = new HashMap<>(); //用于统计字符的入度
    boolean check;

    public String alienOrder(String[] words) {
        // 1、把words中的所有字符添加到in中
        for(String word : words) {
            for(int i = 0;i < word.length();i++) {
                char ch = word.charAt(i);
                in.put(ch,0); // 先进行初始化为0
            }
        }
        // 2、进行建图
        int n = words.length;
        for(int i = 0;i < n;i++) {
            for(int j = i + 1;j < n;j++) {
                //固定一个字符串和其后面的字符串进行比较，来比较出谁的优先级高
                add(words[i],words[j]);
                if(check == true) {
                    return "";
                }
            }
        }

        // 3、进行BFS
        Queue<Character> q = new LinkedList<>();
        // 把入度为0的字符添加到队列中
        for(char ch : in.keySet()) {
            // keySet 可以获取哈希表中全部的key值
            if(in.get(ch) == 0) {
                q.add(ch);
            }
        }

        StringBuilder ret = new StringBuilder(); // 进行拼接字符进行记录返回值
        while(!q.isEmpty()) {
            char t = q.poll();
            ret.append(t);
            if(!edges.containsKey(t)){
                continue;
            }
            for(char ch : edges.get(t)) {
                in.put(ch,in.get(ch) - 1);
                if(in.get(ch) == 0) {
                    q.add(ch);
                }
            }
        }

        for(char ch : in.keySet()) {
            if(in.get(ch) != 0) {
                return "";
            }
        }

        return ret.toString();
    }

    public void add(String s1,String s2) {
        // 比较最小的长度的次数
        int n = Math.min(s1.length(),s2.length());
        int i = 0;
        for(;i < n;i++) {
            char ch1 = s1.charAt(i),ch2 = s2.charAt(i);
            // ch1->ch2
            if(ch1 != ch2) {
                // 进行判断这个 哈希表 中是否有这个关系
                if(!edges.containsKey(ch1)) {
                    edges.put(ch1,new HashSet<>());
                }
                if(!edges.get(ch1).contains(ch2)) {
                    edges.get(ch1).add(ch2);
                    // 入度也要进行增加
                    in.put(ch2,in.get(ch2) + 1);
                }
                break; //找到第一个后，则退出，后面的关系无法确定
            }
        }
        // 全部比较结束之后呢，要进行判断这个是否是符合的
        // 如果s1为abc，s2为ab 那么就不是一个合法的数据
        if(i == s2.length() && i < s1.length()) {
            check = true;
        }
    }
}
